// 排序链表
// 要求时间复杂度O(n*logn)，额外空间复杂度O(1)，还要求稳定性
// 数组排序做不到，链表排序可以
// 测试链接 : https://leetcode.cn/problems/sort-list/
public class SortList {
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    // 时间复杂度O(n*logn)，额外空间复杂度O(1)，有稳定性
    // 注意为了额外空间复杂度O(1)，所以不能使用递归
    // 因为mergeSort递归需要O(log n)的额外空间
    public static ListNode sortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            n++;  //计算链表长度
        }
        /*
        l1 r1表示第一段有序区间
        l2 r2表示第二段排序区间
         */
        ListNode l1,r1,l2,r2;
        ListNode next, lastTemEnd;
        for(int step = 1; step < n; step <<= 1){
            l1 = head;
            r1 = find(l1,step);
            l2 = r1.next;
            r2 = find(l2,step);
            next = r2.next; //记录下一个区域开始位置
            r1.next = null;
            r2.next = null;
            merge(l1,r1,l2,r2);
            head = start;
            lastTemEnd = end;
            while (next != null){
                l1 = next;
                r1 = find(l1,step);
                l2 = r1.next;
                if(l2 == null){
                    lastTemEnd.next = l1;
                    break;
                }
                r2 = find(l2,step);
                next = r2.next;
                r1.next = null;
                r2.next = null;
                merge(l1,r1,l2,r2);
                lastTemEnd.next = start;
                lastTemEnd = end;
            }

        }
        return start;
    }

    public static ListNode find(ListNode begin, int step) {
        while (begin.next != null && --step != 0){
            begin = begin.next;
        }
        return begin;
    }

    public static ListNode start;  //表示排好序的头位置
    public static ListNode end;    //表示排好序的尾位置
    //传过来的两端啊区间都已有序
    public static void  merge(ListNode l1, ListNode r1 , ListNode l2 , ListNode r2){
        ListNode prev;
        if(l1.val <= l2.val) {  //小的结点做合并后的头结点
            start = l1;
            prev = l1;
            l1 = l1.next;

        }else {
            start = l2;
            prev = l2;
            l2 = l2.next;
        }
        while(l1 != null && l2 != null) {
            if(l1.val <= l2.val) {
                prev.next = l1;
                prev = l1;
                l1 = l1.next;
            }else {
                prev.next = l2;
                prev = l2;
                l2 = l2.next;
            }
        }

        if(l1 == null) {
            prev.next = l2;
            end = r2;
        }else {
            prev.next = l1;
            end = r1;
        }
    }
}
